package leetcode8;

public class test45 {
    /**
     * 437. 路径总和 III
     */
    private int ans; // 用于存储符合条件的路径总数

    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> cnt = new HashMap<>();
        cnt.put(0L, 1); // 前缀和为0的初始条件，路径从根节点开始
        dfs(root, 0, targetSum, cnt); // 从根节点开始DFS
        return ans; // 返回符合条件的路径总数
    }

    private void dfs(TreeNode node, long s, int targetSum, Map<Long, Integer> cnt) {
        if (node == null) {
            return; // 如果节点为空，直接返回
        }

        s += node.val; // 更新路径和
        ans += cnt.getOrDefault(s - targetSum, 0); // 检查是否存在满足条件的路径和
        cnt.merge(s, 1, Integer::sum); // 更新当前路径和出现的次数

        dfs(node.left, s, targetSum, cnt); // 递归左子树
        dfs(node.right, s, targetSum, cnt); // 递归右子树

        cnt.merge(s, -1, Integer::sum); // 回溯，恢复当前路径和的状态
    }

}
